

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>Compiler Transformations &mdash; Mosa Project  documentation</title>
  

  
  
  
  

  
  <script type="text/javascript" src="_static/js/modernizr.min.js"></script>
  
    
      <script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
        <script src="_static/jquery.js"></script>
        <script src="_static/underscore.js"></script>
        <script src="_static/doctools.js"></script>
        <script src="_static/language_data.js"></script>
    
    <script type="text/javascript" src="_static/js/theme.js"></script>

    

  
  <link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
  <link rel="stylesheet" href="_static/css/sphinx_prompt_css.css" type="text/css" />
    <link rel="index" title="Index" href="genindex.html" />
    <link rel="search" title="Search" href="search.html" />
    <link rel="next" title="Settings Options" href="settings-options.html" />
    <link rel="prev" title="Compiler Optimizations" href="compiler-optimizations.html" /> 
</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">
    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search" >
          

          
            <a href="index.html" class="icon icon-home"> Mosa Project
          

          
          </a>

          
            
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <p class="caption"><span class="caption-text">Introduction</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="introduction.html">Introduction</a></li>
<li class="toctree-l1"><a class="reference internal" href="getting-started.html">Getting Started</a></li>
<li class="toctree-l1"><a class="reference internal" href="demos.html">Demos</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="faq.html">Frequently Asked Questions (FAQs)</a></li>
</ul>
<p class="caption"><span class="caption-text">Compiler</span></p>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="compiler-design.html">Compiler Design</a></li>
<li class="toctree-l1"><a class="reference internal" href="compiler-optimizations.html">Compiler Optimizations</a></li>
<li class="toctree-l1 current"><a class="current reference internal" href="#">Compiler Transformations</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#transformation">Transformation</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#example-1">Example #1</a></li>
<li class="toctree-l3"><a class="reference internal" href="#example-2">Example #2</a></li>
<li class="toctree-l3"><a class="reference internal" href="#example-3">Example #3</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#functions">Functions</a></li>
</ul>
</li>
</ul>
<p class="caption"><span class="caption-text">Settings</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="settings-options.html">Settings Options</a></li>
<li class="toctree-l1"><a class="reference internal" href="command-line-arguments.html">Command Line Arguments</a></li>
</ul>
<p class="caption"><span class="caption-text">Tools</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="tools.html">MOSA Tools</a></li>
<li class="toctree-l1"><a class="reference internal" href="tool-compiler.html">MOSA Compiler</a></li>
<li class="toctree-l1"><a class="reference internal" href="tool-launcher.html">MOSA Launcher</a></li>
<li class="toctree-l1"><a class="reference internal" href="tool-launcher-console.html">MOSA Launcher Console</a></li>
<li class="toctree-l1"><a class="reference internal" href="tool-explorer.html">MOSA Explorer</a></li>
<li class="toctree-l1"><a class="reference internal" href="tool-debugger.html">MOSA Debugger</a></li>
<li class="toctree-l1"><a class="reference internal" href="tool-boot-image.html">MOSA Boot Image Tool</a></li>
</ul>
<p class="caption"><span class="caption-text">Advanced</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="unit-tests.html">Unit Tests</a></li>
<li class="toctree-l1"><a class="reference internal" href="usb-flash-drive-installation.html">USB Flash Drive Installation</a></li>
<li class="toctree-l1"><a class="reference internal" href="baremetal.html">BareMetal Experiment</a></li>
</ul>
<p class="caption"><span class="caption-text">Contribute</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="get-involved.html">Get Involved</a></li>
<li class="toctree-l1"><a class="reference internal" href="authors.html">Authors</a></li>
<li class="toctree-l1"><a class="reference internal" href="license.html">License</a></li>
</ul>

            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" aria-label="top navigation">
        
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="index.html">Mosa Project</a>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        
          















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="index.html">Docs</a> &raquo;</li>
        
      <li>Compiler Transformations</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
            
            <a href="_sources/compiler-transformations.rst.txt" rel="nofollow"> View page source</a>
          
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <div class="section" id="compiler-transformations">
<h1>Compiler Transformations<a class="headerlink" href="#compiler-transformations" title="Permalink to this headline">¶</a></h1>
<p>MOSA compiler utilitizes a datebase of transformations to represent specific types of optimizations. To make it easy to add new optimizations to the compiler, these transformation are described in text files.</p>
<p>A special parser program reads the json files and translates them into C# source code files, which are then included in the MOSA compiler.</p>
<p>These files are located at <code class="docutils literal notranslate"><span class="pre">Source\Data\IR-Optimization-*.json</span></code>.</p>
<div class="section" id="transformation">
<h2>Transformation<a class="headerlink" href="#transformation" title="Permalink to this headline">¶</a></h2>
<p>Each tranformation has three functional parts: <strong>Expression</strong>, <strong>Filter</strong>, and <strong>Rule</strong>.</p>
<p>The <strong>expression</strong> describes the required expression tree necessary for the rule to execute. The <strong>filter</strong> describes specific attributes of operands in the expression tree that must also be satified for the rule to execute. And the <strong>rule</strong> represents the replacement expression tree.</p>
<div class="section" id="example-1">
<h3>Example #1<a class="headerlink" href="#example-1" title="Permalink to this headline">¶</a></h3>
<p>Here’s an example of a constant folding optimization where an add operation with two constants are translated into a simple move operation.</p>
<div class="highlight-bash notranslate"><div class="highlight"><pre><span></span><span class="o">{</span>
        <span class="s2">&quot;FamilyName&quot;</span>: <span class="s2">&quot;IR&quot;</span>,
        <span class="s2">&quot;Type&quot;</span>: <span class="s2">&quot;ConstantFolding&quot;</span>,
        <span class="s2">&quot;Name&quot;</span>: <span class="s2">&quot;Add32&quot;</span>,
        <span class="s2">&quot;SubName&quot;</span>: <span class="s2">&quot;&quot;</span>,
        <span class="s2">&quot;Expression&quot;</span>: <span class="s2">&quot;IR.Add32 a b&quot;</span>,
        <span class="s2">&quot;Filter&quot;</span>: <span class="s2">&quot;IsResolvedConstant(a) &amp; IsResolvedConstant(b)&quot;</span>,
        <span class="s2">&quot;Result&quot;</span>: <span class="s2">&quot;(IR.Move32 [Add32(To32(a),To32(b))])&quot;</span>
<span class="o">}</span>
</pre></div>
</div>
<p>The first four fields, FamilyName, Type, Name, and SubName, represent a unique name for the transformation.</p>
<p>This is translated into the following C# code:</p>
<div class="highlight-csharp notranslate"><div class="highlight"><pre><span></span><span class="k">public</span> <span class="k">sealed</span> <span class="k">class</span> <span class="nc">Add32</span> <span class="p">:</span> <span class="n">BaseTransformation</span>
<span class="p">{</span>
        <span class="k">public</span> <span class="nf">Add32</span><span class="p">()</span> <span class="p">:</span> <span class="k">base</span><span class="p">(</span><span class="n">IRInstruction</span><span class="p">.</span><span class="n">Add32</span><span class="p">)</span>
        <span class="p">{</span>
        <span class="p">}</span>

        <span class="k">public</span> <span class="k">override</span> <span class="kt">bool</span> <span class="nf">Match</span><span class="p">(</span><span class="n">Context</span> <span class="n">context</span><span class="p">,</span> <span class="n">TransformContext</span> <span class="n">transformContext</span><span class="p">)</span>
        <span class="p">{</span>
                <span class="k">if</span> <span class="p">(!</span><span class="n">IsResolvedConstant</span><span class="p">(</span><span class="n">context</span><span class="p">.</span><span class="n">Operand1</span><span class="p">))</span>
                        <span class="k">return</span> <span class="k">false</span><span class="p">;</span>

                <span class="k">if</span> <span class="p">(!</span><span class="n">IsResolvedConstant</span><span class="p">(</span><span class="n">context</span><span class="p">.</span><span class="n">Operand2</span><span class="p">))</span>
                        <span class="k">return</span> <span class="k">false</span><span class="p">;</span>

                <span class="k">return</span> <span class="k">true</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="k">public</span> <span class="k">override</span> <span class="k">void</span> <span class="nf">Transform</span><span class="p">(</span><span class="n">Context</span> <span class="n">context</span><span class="p">,</span> <span class="n">TransformContext</span> <span class="n">transformContext</span><span class="p">)</span>
        <span class="p">{</span>
                <span class="kt">var</span> <span class="n">result</span> <span class="p">=</span> <span class="n">context</span><span class="p">.</span><span class="n">Result</span><span class="p">;</span>

                <span class="kt">var</span> <span class="n">t1</span> <span class="p">=</span> <span class="n">context</span><span class="p">.</span><span class="n">Operand1</span><span class="p">;</span>
                <span class="kt">var</span> <span class="n">t2</span> <span class="p">=</span> <span class="n">context</span><span class="p">.</span><span class="n">Operand2</span><span class="p">;</span>

                <span class="kt">var</span> <span class="n">e1</span> <span class="p">=</span> <span class="n">transformContext</span><span class="p">.</span><span class="n">CreateConstant</span><span class="p">(</span><span class="n">Add32</span><span class="p">(</span><span class="n">To32</span><span class="p">(</span><span class="n">t1</span><span class="p">),</span> <span class="n">To32</span><span class="p">(</span><span class="n">t2</span><span class="p">)));</span>

                <span class="n">context</span><span class="p">.</span><span class="n">SetInstruction</span><span class="p">(</span><span class="n">IRInstruction</span><span class="p">.</span><span class="n">Move32</span><span class="p">,</span> <span class="n">result</span><span class="p">,</span> <span class="n">e1</span><span class="p">);</span>
        <span class="p">}</span>
<span class="p">}</span>
</pre></div>
</div>
</div>
<div class="section" id="example-2">
<h3>Example #2<a class="headerlink" href="#example-2" title="Permalink to this headline">¶</a></h3>
<p>Here’s an example of a rewrite optimization where three operations are rewriting into two:</p>
<div class="highlight-bash notranslate"><div class="highlight"><pre><span></span><span class="o">{</span>
        <span class="s2">&quot;FamilyName&quot;</span>: <span class="s2">&quot;IR&quot;</span>,
        <span class="s2">&quot;Type&quot;</span>: <span class="s2">&quot;Rewrite&quot;</span>,
        <span class="s2">&quot;Name&quot;</span>: <span class="s2">&quot;And32&quot;</span>,
        <span class="s2">&quot;SubName&quot;</span>: <span class="s2">&quot;Not32Not32&quot;</span>,
        <span class="s2">&quot;Expression&quot;</span>: <span class="s2">&quot;(IR.And32 (IR.Not32 a) (IR.Not32 b))&quot;</span>,
        <span class="s2">&quot;Filter&quot;</span>: <span class="s2">&quot;&quot;</span>,
        <span class="s2">&quot;Result&quot;</span>: <span class="s2">&quot;(IR.Not32 (IR.Or32 a b))&quot;</span>
<span class="o">}</span>
</pre></div>
</div>
</div>
<div class="section" id="example-3">
<h3>Example #3<a class="headerlink" href="#example-3" title="Permalink to this headline">¶</a></h3>
<p>Here’s an example of a strength reduction optimization where a multiplication operation by a power of two is translated into a cheaper shift operation:</p>
<div class="highlight-bash notranslate"><div class="highlight"><pre><span></span><span class="o">{</span>
        <span class="s2">&quot;FamilyName&quot;</span>: <span class="s2">&quot;IR&quot;</span>,
        <span class="s2">&quot;Type&quot;</span>: <span class="s2">&quot;StrengthReduction&quot;</span>,
        <span class="s2">&quot;Name&quot;</span>: <span class="s2">&quot;MulSigned32&quot;</span>,
        <span class="s2">&quot;SubName&quot;</span>: <span class="s2">&quot;ByPowerOfTwo&quot;</span>,
        <span class="s2">&quot;Expression&quot;</span>: <span class="s2">&quot;IR.MulSigned32 x c&quot;</span>,
        <span class="s2">&quot;Filter&quot;</span>: <span class="s2">&quot;IsResolvedConstant(c) &amp; IsPowerOfTwo32(c) &amp; !IsZero(c) &amp; !IsOne(c)&quot;</span>,
        <span class="s2">&quot;Result&quot;</span>: <span class="s2">&quot;(IR.ShiftLeft32 x [GetPowerOfTwo(To32(c))])&quot;</span>
<span class="o">}</span>
</pre></div>
</div>
</div>
</div>
<div class="section" id="functions">
<h2>Functions<a class="headerlink" href="#functions" title="Permalink to this headline">¶</a></h2>
<p>To find the available filter and expression functions, see the methods in the <code class="docutils literal notranslate"><span class="pre">Filter</span> <span class="pre">Methods</span></code> and <code class="docutils literal notranslate"><span class="pre">Expression</span> <span class="pre">Methods</span></code> regions of <code class="docutils literal notranslate"><span class="pre">Source\Mosa.Compiler.Framework\Transform\BaseTransformation.cs</span></code>.</p>
</div>
</div>


           </div>
           
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="settings-options.html" class="btn btn-neutral float-right" title="Settings Options" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right"></span></a>
      
      
        <a href="compiler-optimizations.html" class="btn btn-neutral float-left" title="Compiler Optimizations" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; Copyright 2008-2020, Mosa Project &amp; contributors

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. 

</footer>

        </div>
      </div>

    </section>

  </div>
  


  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script>

  
  
    
   

</body>
</html>